1. Identificação | |
Tipo de Referência | Tese ou Dissertação (Thesis) |
Site | mtc-m21c.sid.inpe.br |
Código do Detentor | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
Identificador | 8JMKD3MGP3W34R/43MTEC5 |
Repositório | sid.inpe.br/mtc-m21c/2020/12.03.19.26 |
Última Atualização | 2021:03.31.16.37.20 (UTC) simone |
Repositório de Metadados | sid.inpe.br/mtc-m21c/2020/12.03.19.26.26 |
Última Atualização dos Metadados | 2022:04.03.23.15.39 (UTC) administrator |
Chave Secundária | INPE-18381-TDI/3043 |
Chave de Citação | Chagas:2021:MeOvCl |
Título | Methods for overlapping clustering optimization problems |
Título Alternativo | Métodos para problemas de otimização de agrupamentos com sobreposição |
Curso | CAP-COMP-DIPGR-INPE-MCTI-GOV-BR |
Ano | 2021 |
Data | 2020-11-30 |
Data de Acesso | 04 maio 2024 |
Tipo da Tese | Tese (Doutorado em Computação Aplicada) |
Tipo Secundário | TDI |
Número de Páginas | 145 |
Número de Arquivos | 1 |
Tamanho | 1786 KiB |
|
2. Contextualização | |
Autor | Chagas, Guilherme Oliveira |
Banca | Korting, Thales Sehn (presidente) Lorena, Luiz Antônio Nogueira (orientador) Santos, Rafael Duarte Coelho dos (orientador) Queiroz, Gilberto Ribeiro de Chaves, Antonio Augusto Coelho, Leandro Callegari |
Endereço de e-Mail | guilherme.o.chagas@gmail.com |
Universidade | Instituto Nacional de Pesquisas Espaciais (INPE) |
Cidade | São José dos Campos |
Histórico (UTC) | 2020-12-03 19:27:28 :: guilherme.chagas@inpe.br -> pubtc@inpe.br :: 2020-12-04 16:24:30 :: pubtc@inpe.br -> guilherme.chagas@inpe.br :: 2020-12-05 18:54:40 :: guilherme.chagas@inpe.br -> administrator :: 2020-12-07 11:29:40 :: administrator -> pubtc@inpe.br :: 2020-12-07 11:30:35 :: pubtc@inpe.br -> guilherme.chagas@inpe.br :: 2020-12-07 18:19:18 :: guilherme.chagas@inpe.br -> administrator :: 2021-03-31 15:00:31 :: administrator -> simone :: 2021-03-31 16:34:33 :: simone :: -> 2020 2021-03-31 16:37:20 :: simone -> administrator :: 2020 2021-04-01 10:37:13 :: administrator -> simone :: 2020 2021-04-28 18:35:32 :: simone :: 2020 -> 2021 2021-04-28 18:35:33 :: simone -> administrator :: 2021 2021-04-28 21:23:24 :: administrator -> simone :: 2021 2021-04-28 21:24:02 :: simone -> administrator :: 2021 2021-12-13 19:16:54 :: administrator -> simone :: 2021 2021-12-13 19:17:49 :: simone -> administrator :: 2021 2022-04-03 23:15:39 :: administrator -> :: 2021 |
|
3. Conteúdo e estrutura | |
É a matriz ou uma cópia? | é a matriz |
Estágio do Conteúdo | concluido |
Transferível | 1 |
Palavras-Chave | overlapping clustering overlap control community detection multiple assignment hybrid heuristic branch-and-price agrupamento com sobreposição controle de sobreposição detecção de comunidades multi-designação heurística híbrida |
Resumo | Clustering problems arise from several areas of science. Approaches and algorithms are as varied as the applications. The goal of clustering is to partition a set of elements into disjoint subsets, also known as clusters, according to a similarity metrics values. In many real-world applications, however, vertices can belong to more than one cluster, i.e., clusters may overlap. Identifying such overlapping clusters is usually a less studied problem and a more challenging task than finding non-overlapping ones. Thus, in this work, overlapping clustering problems from four different contexts are explored. First, it is introduced the overlapping cluster editing, a new relaxation of the cluster editing problem. Three hybrid heuristics were developed to generate solutions for this problem, which are composed of coupling metaheuristics and mixed-integer linear programs. The second work introduces a hybrid heuristic for the overlapping community detection problem, where the objective is to identify overlapping clusters from an input network. This is achieved by solving a mixedinteger linear program using, as input, a heterogeneous set of clusters generated by two state-of-the-art overlapping community detection algorithms. In the third work, the p-median problem with overlap control is introduced. This problem is a variation of the well-known p-median problem, where the objective is to select p facilities vertices whereas the sum of the distances from each client vertex to its nearest facility is minimized. In the p-median problem with overlap control, the number of vertices shared between facilities can be managed from a user-defined parameter. A parallel branch-and-price method was developed to solve this problem. In the fourth work, a parallel adaptive large neighborhood search metaheuristic was proposed to solve some facility location problems with multiple assignments. Several tests results in all problems show that all proposed methods can generate good-quality overlapping clustering solutions. RESUMO: Problemas de agrupamento são encontrados em várias áreas da ciência e abordagens e algoritmos são tão variados quanto as aplicações. O objetivo em um problema de agrupamento é particionar um conjunto de elementos em subconjuntos disjuntos, também conhecidos como clusters. Entretanto, em muitas aplicações de problemas reais, elementos podem pertencer a mais de um cluster, isto é, os clusters podem se sobrepor. Identificar tais clusters sobrepostos é, em geral, um problema menos estudado e mais difícil que o problema original. Então, neste trabalho, problemas de agrupamento com sobreposição, de quatro contextos diferentes, são explorados. No primeiro contexto, é introduzido o problema de edição de clusters com sobreposição, uma nova relaxação do problema de edição de clusters. Três heurísticas híbridas foram desenvolvidas para gerar soluçoes para o problema proposto, as quais são combinações de meta-heurísticas e problemas lineares inteiros mistos. Introduz-se, no segundo trabalho, uma heurística híbrida para o problema de detecção de comunidades com sobreposição. Essa heurística híbrida é composta de um problema linear inteiro misto que recebe, como entrada, um conjunto de clusters gerado por duas heurísticas no estado da arte de detecção de comunidades. No terceiro contexto, o problema de p-medianas com controle de sobreposição é introduzido. Esse problema é uma variação do problema de p-medianas. No problema de p-medianas, o número de vértices compartilhados entre as facilidades pode ser controlado por um parâmetro de entrada. Um algoritmo paralelo de branch-and-price foi implementado para resolver esse problema. No quarto contexto, uma meta-heurística Adaptive Large Neighborhood Search paralela foi aplicada a três problemas de localização de facilidades com multi-designação. Vários testes foram realizados em todos os quatro contextos e os métodos propostos puderam gerar boas soluções de agrupamento com sobreposição. |
Área | COMP |
Arranjo | urlib.net > BDMCI > Fonds > Produção a partir de 2021 > CGIP > Methods for overlapping... |
Conteúdo da Pasta doc | acessar |
Conteúdo da Pasta source | originais/@4primeirasPaginas.pdf | 30/03/2021 11:27 | 411.1 KiB | originais/aprovacao.pdf | 07/12/2020 13:22 | 311.6 KiB | originais/guilhermeChagasThesis.pdf | 07/12/2020 16:01 | 1.1 MiB | originais/guilhermeChagasThesis_Pequenas correcoes.pdf | 07/12/2020 09:01 | 1.2 MiB | |
Conteúdo da Pasta agreement | |
|
4. Condições de acesso e uso | |
URL dos dados | http://urlib.net/ibi/8JMKD3MGP3W34R/43MTEC5 |
URL dos dados zipados | http://urlib.net/zip/8JMKD3MGP3W34R/43MTEC5 |
Idioma | en |
Arquivo Alvo | publicacao.pdf |
Grupo de Usuários | guilherme.chagas@inpe.br pubtc@inpe.br |
Visibilidade | shown |
Licença de Direitos Autorais | urlib.net/www/2012/11.12.15.10 |
Detentor dos Direitos | originalauthor yes |
Permissão de Leitura | allow from all |
Permissão de Atualização | não transferida |
|
5. Fontes relacionadas | |
Repositório Espelho | urlib.net/www/2017/11.22.19.04.03 |
Unidades Imediatamente Superiores | 8JMKD3MGPCW/3F2PHGS 8JMKD3MGPCW/46KUES5 |
Lista de Itens Citando | sid.inpe.br/bibdigital/2013/10.12.22.16 1 |
Acervo Hospedeiro | urlib.net/www/2017/11.22.19.04 |
|
6. Notas | |
Campos Vazios | academicdepartment affiliation archivingpolicy archivist callnumber contenttype copyholder creatorhistory descriptionlevel dissemination doi electronicmailaddress format group isbn issn label lineage mark nextedition notes number orcid parameterlist parentrepositories previousedition previouslowerunit progress readergroup resumeid schedulinginformation secondarydate secondarymark session shorttitle sponsor subject tertiarymark tertiarytype url versiontype |
|